/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***快速排序          P67                       ***/
/***C++ 实现版本    written by Daniel           ***/
#include <iostream>
//用于获取系统时间
#include <ctime>
//用于生成随机数
#include <cstdlib>
using std::cout;
using std::endl;
#define MAX 8000000

void printArr(int *arr, int size)
{
    for (int i = 0; i < size; i++)
    {
        std::cout << arr[i] << "\t";
    }
    std::cout << std::endl;
}

void quickSort(int *arr, int size, int left, int right)
{
    int l = left;
    int r = right;
    int pivot = arr[(left + right) / 2];
    //需要循环在左边找，大于等于pivot的数
    //需要循环在右边找，小于等于pivot的数，然后交换；
    //知道l>r,已经将所有的小于pivot的数，放到了pivot的左边，大于pivot的数，放到了pivot的右边
    int temp = 0;
    while (l < r)
    { //找到左边>=pivot的数
        while (arr[l] < pivot)
        {
            l++;
        }
        //找到右边<=pivot的数
        while (arr[r] > pivot)
        {
            r--;
        } //说明已经找到了中间，交换完成
        if (l >= r)
        {
            break;
        } //交换两个元素的位置

        temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;

        //防止出现死循环
        if (arr[l] == pivot)
        {
            r--;
        }
        if (arr[r] == pivot)
        {
            l++;
        }
    }
    if (l == r)
    {
        l++;
        r--;
    }
    if (left < r)
    {
        quickSort(arr, size, left, r);
    }
    if (l < right)
    {
        quickSort(arr, size, l, right);
    }
}

int main(int argc, char **argv)
{
    //使用系统时间生成一个随机数种子
    srand(time(NULL));
    int *array = new int[MAX];
    for (int i = 0; i < MAX; i++)
    {
        array[i] = rand() % MAX;
        // cout<<array[i]<<endl;
    }
    //printArr(array, MAX);
    time_t now = time(NULL);
    std::cout << "now=" << now << std::endl;
    quickSort(array, MAX, 0, MAX - 1);
    //printArr(array, MAX);
    time_t newNow = time(NULL);
    std::cout << "newNow=" << newNow << std::endl;
    std::cout << "一共花了" << newNow - now << "秒" << endl;
    delete[] array;
    return 0;
}